<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3415：Poi2013 Price List</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013 Price List</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013 Price List</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Poi2013 Price List                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium; ">Railway has always been the most popular mean of transport in Byteotia. Out of N towns in the land, M&nbsp; pairs are connected by track segments belonging to Byteotian State Railways (BSR). The tracks do not cross outside of towns, and may lead through picturesque bridges and somewhat less picturesque tunnels. The ticket for travelling between any two towns directly connected by rail costs a bythalers.<br />
Currently the transportation market in Byteotia is changing. As of now, BSR faces a new competitor: Byteotian Airlines (BA). BA plans to operate flights between some pairs of towns. Since Byteotian railways are quite comfortable, the BA board has decided to operate flights only between pairs of towns that are not directly connected by rail. Due to economy, BA will fly only between towns for which the cheapest railway connection requires exactly one change. The ticket for each such flight is going to cost b bythalers.<br />
To help Byteotian citizens in planning their trips, the Byteotian Ministry for Transport (BMT) has decided to issue leaflets specifying the cheapest routes between all possible towns. A sequence of an arbitrary number of direct railway or airplane connections is called a route. A BMT officer by the name of Byteasar has been commissioned with the task of preparing the price list for the leaflets. Could you help him in writing a program that will determine the right prices?<br />
Let us clarify that all the connections in Byteotia, both by railway and airplane, are bidirectional.<br />
</span></p>
<p><span style="font-size: medium; ">一个n个点m条边的无向联通图，每条边的权值都是a。</span></p>
<p><span style="font-size: medium; ">定义当前图的i与j最短距离为dis[i][j]。</span></p>
<p><span style="font-size: medium; ">现在改造这个图：对于任何满足dis[u][v]=2a的(u,v)，在u与v之间连一条权值为b的无向边</span></p>
<p><span style="font-size: medium; ">原来的权值为a的边保留</span></p>
<p></p></p><hr/><h3>输入格式</h3><p><p><font size="4">The first line of the standard input contains five integers n ,m,k,a and b (2&lt;=N&lt;=100000,1&lt;=M&lt;=100000 1&lt;=K&lt;=N 1&lt;=a,b&lt;=1000<br />
separated by single spaces. The numbers n and m denote the number of towns and the number of direct railway connections in Byteotia, respectively. For simplicity, we number the towns in Byteotia from&nbsp;&nbsp; to n . The other numbers denote:K&nbsp; - the number of the source town for which the connection prices are to be determined; a - the price of a direct railway connection;b - the price of a direct airplane connection.<br />
Each of the following m lines contains a pair of integers Ui and Vi (1&lt;=Ui,Vi&lt;=N Ui&lt;&gt;Vi for i=1,2&hellip;..M<br />
&nbsp;separated by a single space, specifying the number of towns directly connected by tracks.<br />
You may assume that all towns are reachable by railway from the town no.k.<br />
</font></p></p><hr/><h3>输出格式</h3><p><p><font size="4">Your program should print n lines to the standard output. The line no. I for i=1,2,&hellip;.N should contain a single integer: the cost of the cheapest route from town no. k to town no. i. Among those, the line no. k should contain the number 0.<br />
</font></p></p><hr/><h3>样例输入</h3><pre>5 5 1 3 2
1 2
2 3
3 4
4 5
3 1
</pre><hr/><h3>样例输出</h3><pre>0
3
3
2
5


Explanation of the example: The cheapest route from town no. 1 to town no. 5 leads through either town no. 3 or town no. 4. In both cases it consists of a single railway link and a single airplane link.

</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>鸣谢Wcmg提供译文</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3415" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3415" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>